Writing a chess program

The program will be written in Python and contains all main parts of a chess engine.

Every chess program has 3 important parts:

- The representation of the board
- The board evaluation
- The search

As a starting point we use the Python package "chess" https://python-chess.readthedocs.io which is a library for move generation, move validation, support for printing the board and more.

Board representation

The main component of the chess library is a "Board"-object which represents the pieces on the chess board, and has methods for move-generation and checking the status of the board (for example checking for mate). The object has a move-stack on which you can push and pop moves, for making a move and taking back a move.

An SVG component can be used to display a graphical representation of the board as above in a "Jupyter"-notebook.

Board evaluation

A position on the chess board can be evaluated, if it is won by one side or it is a draw. If none of this conditions is satisfied we need an estimate of how likely it is that a player wins. In this simple implementation it is done by two factors the "material" (pieces on board) and the positions of the pieces. For each sort of pieces different values are calculated depending on the squares the pieces are located. This is done with so called "piece-square" tables. See below for the implementation.

The function returns -9999 if white is mated, 9999 if black is mated and 0 for a draw. In all other situations it returns an evaluation as the sum of the material and the sum of postion values via piece-square tables. If black is in turn then the negative value is returned as needed by the negamax implementation of the search (see below).

Piece-square tables

We used the piece-squre tables from https://www.chessprogramming.org/Simplified_Evaluation_Function. For each sort of piece a different table is defined. If the value on a square is positive then the program tries to place a piece on that square if the value is negative it avoids to move to that square. The value of the whole position is calculated by summing over all pieces of both sides.

For pawns the program is encouraged to advance the pawns. Additionally we try to discourage the engine from leaving central pawns unmoved. Pawns on f2, g2 or c2 and b2 should not move zu f3 etc.

Knights are simply encouraged to go to the center. Standing on the edge is a bad idea.

Bishops should avoid corners and borders.

Rooks should occupy the 7th rank and avoid a, h columns

Queens should avoid corners and borders and stay in the center.

Kings should stand behind the pawn shelter. This is only good for opening and middle game. The endgame needs a different table. I will do this in a future enhancement of the program.

Search algorithms

We are using the MinMax algorithm with the Negamax implementation. We are also bringing in alpha beta tuning and quiescence search approach

For lookahead we use Depth-First search that starts at the root and explores up to a fixed depth along each branch before backtracking. The value of the position is calculated via Minimax and Alphabeta pruning is used with the Negamax implementation.

At the maximun search depth the search is extended by searching all capture moves, the so called quiescence search to avoid the "Horizon Effect".

The function which implements the move selection in the root position consists of two parts. The first part tries to find a move in the opening book and gives it back. The "chess" library has a function to access opening books in the "Polyglot" format. I used the "bookfish" opening book which I downloaded from http://rebel13.nl/download/books.html. A random weighted move is selected from all possible moves of the book in this position.

The second part calculates the move if the book is empty. For each move in the position the search (alphabeta) is conducted and the best move is choosen.

Another search version using only the alphabeta pruning without the quiescence search. It is used for testing purposes

With this search version, we omit the alpha beta pruning in order to compare the different algorithms performances

Play against computer

To play against the program inside a Jupyter notebook you can evalute the following cell to compute a computer move (with a search depth of 3), and display the board.

To make a human move you can use:

Selfplay and Tests

In this section, we test the different approaches : Quiescence_Search, alpha beta pruning and minmax only.

Different tests have been conducted, the full game plays are shown below.

Negamax vs Negamax - same depth

In the following, Negmax is playing against Negamax with the same max research depth for each player

Negamax vs Negamax - depth : 4 - 3

In the following, Negmax with max depth 4 is playing agaist Negamax with max depth 3

Negamax_ab vs Negamax_ab

In the following, the players are using the alpha beta pruning

Negamax_ab - Negamax_ab - depth : 3 - 4

Next, we're testing the max depth effect on the alpha beta pruning

Quiescence vs Quiescence - same depth

Below, 2 quiescence search algorithms are confronting each other with max search depth of 3 for the minmax

Quiescence vs Negamax_ab

In the following, quiescence search in confronting the alpha beta tuning

Negamaxab vs Quiescence

We perform the reverse test : White is using the quiescence search approach Black is using the Negamax_ab algorithm

Quies vs Quies : with cuts count

We are trying to increase max depth search

Move Ordering

In this section, we order the legal moves based on their outcome

MinMax Score move order

Search with order

ordering functions

Testing minmax move order

Promising move order

Move evaluation function

Search algorithms

Testing

Testing order vs non order